#include <unordered_map>
#include <array>
#include <string>
using namespace std;
// 变种tire 树+递归搜索
class tire_node
{
    friend class tire_tree;

public:
    friend class tire_tree;
    tire_node(const char ch = '\0') : c(ch)
    {
        sons.fill(nullptr);
    }

private:
    char c;
    unordered_map<string, int> end_map;
    array<tire_node *, 26> sons;
};
class tire_tree
{
public:
    void insert(const string &str, const int val)
    {
        tire_node *cur = root;
        for (auto c : str)
        {
            if (!cur->sons[c - 'a'])
                cur->sons[c - 'a'] = new tire_node(c);
            cur = cur->sons[c - 'a'];
        }
        cur->end_map[str] = val;
    }
    int get_sum(const string &prefix)
    {
        tire_node *cur = root;
        for (auto c : prefix)
        {
            if (!cur->sons[c - 'a'])
                return 0;
            cur = cur->sons[c - 'a'];
        }
        return add_all_path(cur);
    }

private:
    int add_all_path(tire_node *cur)
    {
        int res = 0;
        // 获取拉链
        for (auto it = cur->end_map.begin(); it != cur->end_map.end(); it++)
            res += it->second;
        for (int i = 0; i < 26; i++)
        {
            if (cur->sons[i])
                res += add_all_path(cur->sons[i]);
        }
        return res;
    }
    tire_node *root = new tire_node;
};
class MapSum
{
private:
    tire_tree tire;

public:
    /** Initialize your data structure here. */
    MapSum()
    {
    }

    void insert(string key, int val)
    {
        tire.insert(key, val);
    }

    int sum(string prefix)
    {
        return tire.get_sum(prefix);
    }
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */